package algorithm.leetcode.I201to400;

import algorithm.leetcode.TreeNode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Q236 {

    Map<Integer, TreeNode> fathers = new HashMap<>();

    private void findAllNodeFather(TreeNode root) {
        if (root.left != null) {
            fathers.put(root.left.val, root);
            findAllNodeFather(root.left);
        }
        if (root.right != null) {
            fathers.put(root.right.val, root);
            findAllNodeFather(root.right);
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        findAllNodeFather(root);
        Stack<TreeNode> pStack = new Stack<>();
        if (p != null) pStack.push(p);
        Stack<TreeNode> qStack = new Stack<>();
        if (q != null) qStack.push(q);
        int pVal = p.val, qVal = q.val;

        while (fathers.containsKey(pVal)) {
            pStack.push(fathers.get(pVal));
            pVal = fathers.get(pVal).val;
        }
        while (fathers.containsKey(qVal)) {
            qStack.push(fathers.get(qVal));
            qVal = fathers.get(qVal).val;
        }
        TreeNode treeNode = null;
        while (!qStack.isEmpty() && !pStack.isEmpty() && qStack.peek() == pStack.peek()) {
            treeNode = qStack.pop();
            pStack.pop();
        }
        return treeNode;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(6);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(0);
        TreeNode node7 = new TreeNode(8);
        TreeNode node8 = new TreeNode(7);
        TreeNode node9 = new TreeNode(4);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node5.left = node8;
        node5.right = node9;

        Q236 twoThreeSix = new Q236();
        System.out.println(twoThreeSix.lowestCommonAncestor(node1, node2, node9));
    }

}